package lk;

import java.util.*;

import lk.D231001.TreeNode;

public class D231002 {
    // 二叉树的右视图

    // 1. 广度优先搜索
    // 层序遍历，将每层的最后一个节点，加入结果集
    // 使用了 队列
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {
                    res.add(node.val);
                }
            }
        }
        return res;
    }

    // 2. 深度优先搜索
    // 搜索过程中，总是先访问右节点，那么对于每一层来说，第一个访问的节点一定是最右边的节点
    // 使用了栈
    public List<Integer> rightSideView2(TreeNode root) {
        List<Integer> rightView = new ArrayList<Integer>(); // 记录结果
        int maxDepth = -1;  // 记录遍历到的最深深度

        Deque<TreeNode> nodeStack = new LinkedList<TreeNode>(); // 存储节点的值
        Deque<Integer> depthStack = new LinkedList<Integer>();  // 存储节点的深度

        // 存入根节点
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.isEmpty()) {
            // 弹出节点
            TreeNode node = nodeStack.pop();
            int depth = depthStack.pop();

            // 不为空
            if (node != null) {

                // 是否是最新深度
                if (depth > maxDepth) {
                    maxDepth = depth;
                    rightView.add(node.val);
                }

                // 存入左右节点
                nodeStack.push(node.left);
                nodeStack.push(node.right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }

        return rightView;
    }
}
